#include <algorithm>
#include <vector>
#include <limits>
using namespace std;
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int n=triangle.size();
        if (n==0) return 0;
        vector<int> f(n, numeric_limits<int>::max());
        f[0]=triangle[0][0];
        for (int i=1;i<n;i++) {
            for (int j=i;j>=1;j--)
                f[j]=min(f[j], f[j-1])+triangle[i][j];
            f[0]=f[0]+triangle[i][0];
        }
        int ans=numeric_limits<int>::max();
        for (int i=0;i<n;i++) ans=min(ans,f[i]);
        return ans;
    }
};
